1. Field of the Invention
The present invention relates generally to computational circuits and methods, and particularly to efficient modular computations.
2. Description of Related Art
In Elliptic Curve Cryptography (ECC), arithmetic operations are performed over the points on a chosen elliptic curve. These points can be represented in the standard, canonical form as pairs of numbers (x,y) satisfying a specified equation. In most cases this equation can be written in the short Weierstrass form as y2=x3+A*x+B, wherein A and B are constants that define the elliptical curve. The numbers A, B, x and y are taken from a fixed finite field, such as the field of integers with modulus M, wherein M is a large prime number, and operations on the numbers are performed over this field.
In general, ECC algorithms involve two operations that are performed over the points of a chosen elliptic curve:Point addition: (x1,y1)+(x2,y2)=(x3,y3)Point doubling: 2(x1,y1)=(x3,y3)The straightforward definition of these operations involves modular division, which is a heavy, time-consuming operation.
Therefore, it is common practice to represent the points on the elliptic curve in alternative coordinates that allow the point addition and point doubling operations to be performed as a sequence of modular additions and multiplications. Jacobian coordinates are widely used for this purpose, wherein each point (x,y) on the elliptic curve is represented by three numbers (X,Y,Z), chosen such that the original elliptic coordinates x and y can be expressed as quotients of powers of the alternative coordinates X, Y and Z:
      x    =          X              Z        2              ,      y    =          Y              Z        3            Other representations that can be used in a similar way to enhance computation efficiency over elliptic curves include projective coordinates (in which x=X/Z and y=Y/Z); W12 coordinates (x=X/Z, y=Y/Z2); XYZZ coordinates (x=X/ZZ, y=Y/ZZZ, and ZZ3=ZZZ2); and XZ coordinates (x=X/Z). Representations of this sort are referred to in the present description and in the claims as “quotient-based representations,” since each of the elliptic coordinates x and y is represented as a quotient of certain powers of the alternative coordinates. Further information regarding such representations and their use in elliptic curve computations is available on the hyperelliptic.org Web site.
Even in Jacobian coordinates, however, elliptic curve computations are time-consuming. The classical method of calculating a modular product involves first multiplying the operands as non-modular integers and then taking the modulus of the result, referred to as “modular reduction.” Modular reduction itself is computationally expensive, equivalent to long division. Point doubling and point addition involve many such operations.
For this reason, cryptographic computations often use a more efficient method, known as Montgomery modular multiplication (or simply Montgomery multiplication). To perfon in Montgomery multiplication, the operands are converted to a special Montgomery form using an algorithm known as Montgomery reduction. Multiplication of the operands in Montgomery form avoids the need for modular reduction as required in conventional arithmetic. The Montgomery reduction and multiplication algorithms are described, for example, by Menezes et al., in the Handbook of Applied Cryptography (1996), section 14.3.2, pages 600-603, which is incorporated herein by reference.
To summarize briefly, given two large integers A and B, instead of calculating A*B, Montgomery multiplication produces A⊙B=A*B*R−1% M, wherein R is a constant depends on the length of the modulus M. (The symbol “%” is used in the present description and in the figures to denote “modulo.”) For this purpose, the input operands are first preprocessed (referred to as converting the operands to the Montgomery domain or to Montgomery form), so that each input X is converted to X′=X*R % M. The Montgomery-form operands are then multiplied together as follows:A′⊙B′=A*R*B*R*R−1% M=(A*B)′% M. 
A chain of calculations can be perfoiined in this manner in the Montgomery domain. The final result Res′ is then converted back to integer form using Montgomery multiplication by 1: Res′ ⊙1=Res*R*R−1% M=Res.